package demo.practice.leetcode_offer;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Offer12Trie {

    Integer maxHeight;


    public Offer12Trie() {

    }


    Map<Character, Offer12Trie> child = new HashMap<>();

    public void insert(char[][] board, int heght, char head) {
        this.maxHeight = heght;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == head) {
                    insertRight(board, i, j, 0, new HashSet<>(), this);
                }
            }
        }
    }

    private void insertRight(char[][] board, int i, int j, int heght, Set<String> location, Offer12Trie t) {

        if (location.contains(i + "_" + j) || heght >= maxHeight)
            return;

        char c = board[i][j];
        if (!t.child.containsKey(c)) {
            t.child.put(c, new Offer12Trie());
        }

        Offer12Trie cur = t.child.get(c);

        HashSet<String> l = new HashSet<>(location);
        l.add(i + "_" + j);
        if (i + 1 < board.length) {
            insertRight(board, i + 1, j, heght + 1, new HashSet<>(l), cur);
        }

        if (i - 1 >= 0) {
            insertRight(board, i - 1, j, heght + 1, new HashSet<>(l), cur);
        }

        if (j - 1 >= 0) {
            insertRight(board, i, j - 1, heght + 1, new HashSet<>(l), cur);
        }

        if (j + 1 < board[i].length) {
            insertRight(board, i, j + 1, heght + 1, new HashSet<>(l), cur);
        }
    }


    public boolean find(String word) {
        Offer12Trie cur= this;
        for (char c : word.toCharArray()) {

            if(cur.child.containsKey(c)){
                cur=cur.child.get(c);
            }else{
                return false;
            }
        }

        return true;

    }
}


public class Offer12 {


    public static void main(String[] args) {
        /**
         * [["b","a","a","b","a","b"],["a","b","a","a","a","a"],["a","b","a","a","a","b"],["a","b","a","b","b","a"],["a","a","b","b","a","b"],["a","a","b","b","b","a"],["a","a","b","a","a","b"]]
         * "aabbbbabbaababaaaabababbaaba"
         */

        Offer12 offer12= new Offer12();
        offer12.exist(new char[][]{{'b','a','a','b','a','b'},{'a','b','a','a','a','b'},{'a','b','a','a','a','b'},{'a','b','a','b','b','a'},{'a','a','b','b','a','b'},{'a','a','b','b','b','a'},{'a','a','b','a','a','b'}},"aabbbbabbaababaaaabababbaaba");

    }
    public boolean exist(char[][] board, String word) {
        Offer12Trie trie= new Offer12Trie();
        trie.insert(board,word.length(),word.charAt(0));
        return trie.find(word);
    }



}
